package com.springchang.leetcode.array;

import java.util.Arrays;

/**
 * leetcode 88题：合并有序数组
 */
public class MergeSortedArray_88 {

    public static void merge(int[] nums1, int m, int[] nums2, int n) {

        int[] temp = new int[m+n];

        //合并有序数组，使用双指针的方式
        int index1 = 0;
        int index2 = 0;
        for (int i = 0; i < m+n; i++) {
            if(index2 >= n) {
                //如果nums2已经没有数据了，则加入nums1
                temp[i] = nums1[index1++];
            } else if(index1 >= m) {
                //如果nums1已经没有数据了，则加入nums2
                temp[i] = nums2[index2++];
            } else if(nums1[index1] < nums2[index2]) {
                // nums1当前数值小于nums2当前数值
                temp[i] = nums1[index1++]; //指针后移
            } else {
                temp[i] = nums2[index2++];
            }
        }

        //复制数组的内容
        System.arraycopy(temp, 0, nums1, 0, m+n);
    }

    /*空间复杂度更少的算法，从尾部开始遍历，逆序*/
    public static void mergeLessThanSpace(int[] nums1, int m, int[] nums2, int n) {

        //合并有序数组，使用双指针的方式
        int index1 = m-1;
        int index2 = n-1;
        for (int i = m+n-1; i >= 0; ) {
            if(index1 < 0) {
                //nums1已经结束了，则全部由nums2加入
                nums1[i--] = nums2[index2--];
            } else if(index2 < 0) {
                //num2已经结束，则全部有nums1加入
                nums1[i--] = nums1[index1--];
            } else if(nums1[index1] > nums2[index2]) {
                nums1[i--] = nums1[index1--];
            } else {
                nums1[i--] = nums2[index2--];
            }
        }
    }

    public static void main(String[] args) {

        int[] nums1 = new int[]{1,2,3,0,0,0};
        int m = 3;
        int[] nums2 = new int[]{2,5,6};
        int n = 3;

        mergeLessThanSpace(nums1, m, nums2, n);

        System.out.println(String.format("合并后的数组: %s", Arrays.toString(nums1)));
    }
}
